TNotes.leetcode

Appearance

⏰0820. 单词的压缩编码【中等】

0820. 单词的压缩编码【中等】 ​

1. 📝 题目描述 ​

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

  • words.length == indices.length
  • 助记字符串 s 以 '#' 字符结尾
  • 对于每个下标 indices[i]，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给你一个单词数组 words，返回成功对 words 进行编码的最小助记字符串 s 的长度。

示例 1：

txt
输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5]。
words[0] = "time"，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me"，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell"，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

示例 2：

txt
输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0]。

提示：

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i] 仅由小写字母组成

2. 🎯 s.1 - 后缀去重 ​

c
void reverseStr(char* s, int n) {
    for (int i = 0; i < n / 2; i++) { char t = s[i]; s[i] = s[n-1-i]; s[n-1-i] = t; }
}

int cmpStr(const void* a, const void* b) { return strcmp(*(char**)a, *(char**)b); }

int minimumLengthEncoding(char** words, int wordsSize) {
    char** rev = (char**)malloc(sizeof(char*) * wordsSize);
    for (int i = 0; i < wordsSize; i++) {
        int len = strlen(words[i]);
        rev[i] = (char*)malloc(len + 1);
        strcpy(rev[i], words[i]);
        reverseStr(rev[i], len);
    }
    qsort(rev, wordsSize, sizeof(char*), cmpStr);
    int res = 0;
    for (int i = 0; i < wordsSize; i++) {
        if (i + 1 < wordsSize && strncmp(rev[i], rev[i+1], strlen(rev[i])) == 0) continue;
        res += strlen(rev[i]) + 1;
    }
    for (int i = 0; i < wordsSize; i++) free(rev[i]);
    free(rev);
    return res;
}
js
/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function (words) {
  const set = new Set(words)
  for (const word of words)
    for (let i = 1; i < word.length; i++) set.delete(word.slice(i))
  let res = 0
  for (const word of set) res += word.length + 1
  return res
}
py
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        s = set(words)
        for word in words:
            for i in range(1, len(word)):
                s.discard(word[i:])
        return sum(len(w) + 1 for w in s)
  • 时间复杂度：O(∑wi2)，其中 wi 是每个单词的长度
  • 空间复杂度：O(∑wi)

算法思路：

  • 将所有单词加入集合，然后对每个单词删除其所有后缀
  • 剩余的单词即为不能被其它单词覆盖的，累加长度 + 1